Given an array of integers preorder, which represents the preorder traversal of a BST (i.e., binary search tree), construct the tree and return its root.
It is guaranteed that there is always possible to find a binary search tree with the given requirements for the given test cases.
A binary search tree is a binary tree where for every node, any descendant of Node.left has a value strictly less than Node.val, and any descendant of Node.right has a value strictly greater than Node.val.
A preorder traversal of a binary tree displays the value of the node first, then traverses Node.left, then traverses Node.right.
Example 1:
Input: preorder = [8,5,1,7,10,12] Output: [8,5,10,1,7,null,12]
Example 2:
Input: preorder = [1,3] Output: [1,null,3]
Constraints:
1 <= preorder.length <= 1001 <= preorder[i] <= 108- All the values of
preorderare unique.
Average Rating: 4.54 (43 votes)
Solution
Approach 1: Construct binary tree from preorder and inorder traversal
Intuition
This approach is not the optimal one because of O(NlogN) time complexity, but very straightforward.
Let's use here two facts:
-
Binary tree could be constructed from preorder and inorder traversal.
-
Inorder traversal of BST is an array sorted in the ascending order.
Algorithm
-
Construct inorder traversal by sorting the preorder array.
-
Construct binary tree from preorder and inorder traversal: the idea is to peek the elements one by one from the preorder array and try to put them as a left or as a right child if it's possible. If it's impossible - just put
nullas a child and proceed further. The possibility to use an element as a child is checked by an inorder array: if it contains no elements for this subtree, then the element couldn't be used here, and one should usenullas a child instead.
Implementation
Complexity Analysis
- Time complexity : O(NlogN). O(NlogN) to sort preorder array and O(N) to construct the binary tree.
- Space complexity : O(N) the inorder traversal and the tree.
Approach 2: Recursion
Intuition
It's quite obvious that the best possible time complexity for this problem is O(N) and hence the approach 1 is not the best one.
Basically, the inorder traversal above was used only to check if the element could be placed in this subtree. Since one deals with a BST here, this could be verified with the help of lower and upper limits for each element as for the validate BST problem. This way there is no need in inorder traversal and the time complexity is O(N).
Algorithm
-
Initiate the lower and upper limits as negative and positive infinity because one could always place the root.
-
Start from the first element in the preorder array
idx = 0. -
Return
helper(lower, upper):-
If the preorder array is used up
idx = nthen the tree is constructed, return null. -
If current value
val = preorder[idx]is smaller then lower limit, or larger than upper limit, return null. -
If the current value is in the limits, place it here
root = TreeNode(val)and proceed to construct recursively left and right subtrees:root.left = helper(lower, val)androot.right = helper(val, upper). -
Return
root.
-
Implementation
Complexity Analysis
- Time complexity : O(N) since we visit each node exactly once.
- Space complexity : O(N) to keep the entire tree.
Approach 3: Iteration
Algorithm
The recursion above could be converted into the iteration with the help of stack.
-
Pick the first preorder element as a root
root = new TreeNode(preorder[0])and push it into stack. -
Use
forloop to iterate along the elements of preorder array :-
Pick the last element of the stack as a parent node, and the the current element of preorder as a child node.
-
Adjust the parent node : pop out of stack all elements with the value smaller than the child value. Change the parent node at each pop
node = stack.pop(). -
If
node.val < child.val- put the child as a right child of the node :node.right = child. -
Else - as a left child :
node.left = child. -
Push child node into the stack.
-
-
Return
root.
Implementation
Complexity Analysis
-
Time complexity : O(N) since we visit each node exactly once.
-
Space complexity : O(N) to keep the stack and the tree.
Last Edit: May 10, 2019 1:19 PM
Please stop using Stack class in Java. Here (leetcode.com/problems/flatten-nested-list-iterator/discuss/80147/Simple-Java-solution-using-a-stack-with-explanation/165585) you can find a great explanation of why it's a bad idea and it might even cost you an offer.
There's an unhealthy obsession with Stack and LinkedList classes on Leetcode - 2 classes that nobody uses in real life.
May 25, 2019 2:45 AM
why we can not just use insert method to creat a new BST, which is the answer?
April 28, 2020 11:17 PM
In approach 2, the use of the lower bound is not necessary at all. Surprised the author dares to write "It's quite obvious that the best possible time complexity for this problem is O(N) " but does not realize the "obvious" facts that:
- we have a BST
- we have a preorder of that BST
Meaning that because you are going left first by default tree traversal pattern, then you are guaranteed to have placed the least element first. So only need to check the upper limit.
class Solution {
int idx = 0;
int[] preorder;
int n;
public TreeNode helper(int upper) {
// if all elements from preorder are used
// then the tree is constructed
if (idx == n) return null;
int val = preorder[idx];
// if the current element
// couldn't be placed here to meet BST requirements
if (val > upper) return null;
// place the current element
// and recursively construct subtrees
idx++;
TreeNode root = new TreeNode(val);
root.left = helper(val);
root.right = helper(upper);
return root;
}
public TreeNode bstFromPreorder(int[] preorder) {
this.preorder = preorder;
n = preorder.length;
return helper(Integer.MAX_VALUE);
}
}
"obvious" .... smh...
not really
January 20, 2020 7:09 AM
@andvary @liaison How come space complexity for Solution 3 is O(N)? While adding any new node, we might have to pop logN amount of node. Doesn't that make it O(NlogN)?
Last Edit: December 7, 2019 2:58 PM
Recall the basic question of BST, #701 Insert into a Binary Search Tree
Here was my 1st attempt in python
"""
1st: recursion
- reuse lc701: Insert into a Binary Search Tree
- for each element in the array
- do lc701
Time from O(N) to O(NlogN), because the number of nodes of result tree < N during the construction of it
Space O(N)
12 ms, faster than 99.45%
"""
class Solution(object):
def bstFromPreorder(self, preorder):
res = None
for x in preorder:
res = self.insertIntoBST(res, x)
return res
def insertIntoBST(self, root, val):
if root == None:
return TreeNode(val)
if val < root.val:
root.left = self.insertIntoBST(root.left, val)
else:
root.right = self.insertIntoBST(root.right, val)
return root
Here was my second attempt with iteration
"""
2nd: same concept but with iteration
- reuse lc701: Insert into a Binary Search Tree
- for each element in the array
- do lc701
Time from O(N) to O(NlogN), because the number of nodes of result tree < N during the construction of it
Space O(N)
20 ms, faster than 84.85%
"""
class Solution(object):
def bstFromPreorder(self, preorder):
res = None
for x in preorder:
res = self.insertIntoBST(res, x)
return res
def insertIntoBST(self, root, val):
if root == None:
return TreeNode(val)
cur = root
while True:
if cur.val < val:
if cur.right != None:
cur = cur.right
else:
cur.right = TreeNode(val)
break
else:
if cur.left != None:
cur = cur.left
else:
cur.left = TreeNode(val)
break
return root
Last Edit: October 4, 2020 6:47 PM
Isn't it a bit overcomplicated of approach 1 to just get a O(NlogN) solution?
We can easily get a O(NlogN) solution with this:
class Solution {
public:
TreeNode* bstFromPreorder(vector<int>& preorder) {
return helper(preorder,0,preorder.size()-1);
}
TreeNode* helper(vector<int>& preorder, int i, int j)
{
if(i>j) return nullptr;
if(i==j) return new TreeNode(preorder[i]);
TreeNode* root=new TreeNode(preorder[i]);
int k=i+1;
while(k<=j && preorder[k]<preorder[i]) k++;
root->left=helper(preorder,i+1,k-1);
root->right=helper(preorder,k,j);
return root;
}
};
In approach 2 we don't need to track lower and upper. We can only keep track of the upper. I stand to be corrected but this is what I did and it worked. The code is in Javascript:
var bstFromPreorder = function(preorder) {
let i = 0
function dfs(max){
if(i == preorder.length) return null
if(preorder[i] >= max) return null
let root = new TreeNode(preorder[i])
i++
root.left = dfs(root.val)
root.right = dfs(max)
return root
}
return dfs(10e9)
};
https://leetcode.com/articles/construct-binary-tree-from-preorder-and-inorder-tr/ link is not working.
October 10, 2020 6:53 PM
Approach 3 solution and animation is really good. Helps you understand in a very simple way. Thanks! :)
Last Edit: January 17, 2020 8:23 AM
Can someone explain how the complexity is O(N) for the third solution? To insert 10, for example, the code will pop 7 & 5 and thus it will do logN work. So the order should be O(NlogN) in worst case, right?
x
/** * Definition for a binary tree node. * struct TreeNode { * int val; * TreeNode *left; * TreeNode *right; * TreeNode() : val(0), left(nullptr), right(nullptr) {} * TreeNode(int x) : val(x), left(nullptr), right(nullptr) {} * TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {} * }; */class Solution {public: TreeNode* bstFromPreorder(vector<int>& preorder) { int i = 0; return build(preorder, i, INT_MAX); } TreeNode* build(vector<int>& preorder, int& i, int maxBound) { if (i == preorder.size() || preorder[i] > maxBound) return NULL; TreeNode* root = new TreeNode(preorder[i]); i++; // for left, max bound is the current root's value root->left = build(preorder, i, root->val); // for right, max bound is the maxBound variable root->right = build(preorder, i, maxBound); return root; }};
